package com.langsin.RadixDemo;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @Auther: MFM
 * @Date: 2021/8/16 - 08 - 16 - 17:29
 * @version: 1.0
 */

public class RadixSort {

    /**
     * 进行基数排序
     *
     * @param arr 待排序数组
     */
    public static void sort(int[] arr) {
        //先表示一下 这十个桶
        //考虑到可能所有的数都会在一个桶里这种极端情况，所以每个桶的分配空间为arr.length

        int[][] bucket = new int[10][arr.length];

        //每个元素代表着对应下标+1的桶里有多少个元素
        int[] bucketElementCounts = new int[10];

        int max = arr[0];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }

        int maxLength = (max + "").length();

        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //取位数
            for (int j = 0; j < arr.length; j++) {
                int digitOfElement = arr[j] / n % 10;
                bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
                bucketElementCounts[digitOfElement]++;
            }

            int index = 0;
            for (int j = 0; j < bucketElementCounts.length; j++) {
                if (bucketElementCounts[j] != 0) {
                    for (int k = 0; k < bucketElementCounts[j]; k++) {
                        arr[index] = bucket[j][k];
                        bucket[j][k] = 0;//正确 没必要 有 bucketElementCounts 限制
                        index++;
                    }
                }
                bucketElementCounts[j] = 0;
            }
        }

//        //取个位   将每个元素放入对应桶内
//        for (int i = 0; i < arr.length; i++) {
//            //取出每个元素的个位数
//            int digitOfElement = arr[i] / 1 % 10;
//            //根据取出来的个位数放到对应桶内
//            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];
//
//            bucketElementCounts[digitOfElement]++;
//        }
//
//        int index = 0;//放回arr时用到的下标
//        //按照桶内顺序依次取出数据，放入原来的数组
//        for (int i = 0; i < bucketElementCounts.length; i++) {
//            if (bucketElementCounts[i] != 0) {
//                //将桶内的元素放回
//                for (int j = 0; j < bucketElementCounts[i]; j++) {
//                    arr[index] = bucket[i][j];
//                    index++;
//                }
//            }
//            //此处很重要，放回去之后，需要将每个桶的元素归零
//            bucketElementCounts[i] = 0;
//        }
//
//        System.out.println("取完个位之后的基数排序" + Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = new int[10000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 100000000);
        }

        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("HH:mm:ss");
        String date1str = simpleDateFormat.format(date1);
        System.out.println("归并排序前时间" + date1str);

        sort(arr);

        Date date2 = new Date();
        String date2str = simpleDateFormat.format(date2);
        System.out.println("归并排序后时间" + date2str);

    }
}
